
#include "stdafx.h"
#include "Utils.h"


#define M 4
#define INFINITE INT32_MAX
int t, n, x, y, max;
struct Platform {
	int Lx, Rx, h;
};
Platform aPlatform[M];
int aLeftMinTime[M];
int aRightMinTime[M];

int MinTime(int L, bool bLeft) {
	int y = aPlatform[L].h;
	int x;
	if (bLeft)
		x = aPlatform[L].Lx;
	else
		x = aPlatform[L].Rx;

	//Find the first platform
	int i;
	for (i = L + 1; i <= n; i++) {
		if (aPlatform[i].Lx <= x && aPlatform[i].Rx >= x)
			break;
	}
	
	if (i <= n) //Found platform i
	{
		if (y - aPlatform[i].h > max) //too high, dead
			return INFINITE;
	}
	else { //arrive the floor 0
		if (y > max) //too high, dead
			return INFINITE;
		else
			return y;
	}

	int nLeftTime = y - aPlatform[i].h + x - aPlatform[i].Lx;
	int nRightTime = y - aPlatform[i].h + aPlatform[i].Rx - x;

	if (aLeftMinTime[i] == -1)
		aLeftMinTime[i] = MinTime(i, true);
	
	if (aRightMinTime[i] == -1)
		aRightMinTime[i] = MinTime(i, false);

	nLeftTime += aLeftMinTime[i];
	nRightTime += aRightMinTime[i];

	if (nLeftTime < nRightTime)
		return nLeftTime;
	return nRightTime;
}

int MyCompare(const void* e1, const void* e2) {
	Platform* p1, *p2;
	p1 = (Platform*)e1;
	p2 = (Platform*)e2;

	return p2->h - p1->h;
}

#ifdef TEST_BED
int main()
#else
int main_()
#endif
{
	//init
	t = 1;
	n = 3;
	max = 20;

	aPlatform[0].Lx = 8;
	aPlatform[0].Rx = 8;
	aPlatform[0].h = 17;
	aPlatform[1].Lx = 0;
	aPlatform[1].Rx = 10;
	aPlatform[1].h = 8;
	aPlatform[2].Lx = 0;
	aPlatform[2].Rx = 10;
	aPlatform[2].h = 13;
	aPlatform[3].Lx = 4;
	aPlatform[3].Rx = 14;
	aPlatform[3].h = 3;

	for (int i = 0; i < t; i++) {
		memset(aLeftMinTime, -1, sizeof(aLeftMinTime));
		memset(aRightMinTime, -1, sizeof(aRightMinTime));
		
		qsort(aPlatform, n + 1, sizeof(Platform), MyCompare);
	}

	//aPlatform[i+1]
	//aLeftMinTime[M - 1] = aPlatform[M - 1].h;
	//aRightMinTime[M - 1] = aPlatform[M - 1].h;
	for (int i = M - 1; i >= 0; i--) {
		//aPlatform[i]
		int y = aPlatform[i].h;

		//Left
		//aLeftMinTime[i]
		int x = aPlatform[i].Lx;
		for (int j = i; j < M; j++) {
			int k;
			//Find the first platform underneath
			for (k = i + 1; k < M; k++) {
				if (aPlatform[k].Lx <= x && aPlatform[k].Rx >= x)
					break;
			}

			if (k < M) //Found Platform k
			{
				//aPlatform[k]
				if (y - aPlatform[k].h > max) //too high, dead
					aLeftMinTime[i] = INFINITE;
				else
				{
					aLeftMinTime[i] = (y - aPlatform[k].h) +
						MIN(aLeftMinTime[k] + (x - aPlatform[k].Lx), \
							aRightMinTime[k] + (aPlatform[k].Rx - x));
				}
			}
			else { //arrive floor 0
				if (y > max) //too high, dead
					aLeftMinTime[i] = INFINITE;
				else
					aLeftMinTime[i] = y;
			}
		}

		//Right
		//aRightMinTime[i]
		x = aPlatform[i].Rx;
		for (int j = i; j < M; j++) {
			int k;
			//Find the first platform underneath
			for (k = i + 1; k < M; k++) {
				if (aPlatform[k].Lx <= x && aPlatform[k].Rx >= x)
					break;
			}

			if (k < M) //Found Platform k
			{
				//aPlatform[k]
				if (y - aPlatform[k].h > max) //too high, dead
					aRightMinTime[i] = INFINITE;
				else
				{
					aRightMinTime[i] = (y - aPlatform[k].h) +
						MIN(aLeftMinTime[k] + (x - aPlatform[k].Lx), \
							aRightMinTime[k] + (aPlatform[k].Rx - x));
				}
			}
			else { //arrive floor 0
				if (y > max) //too high, dead
					aRightMinTime[i] = INFINITE;
				else
					aRightMinTime[i] = y;
			}
		}
	}
	
	getchar();

    return 0;
}


